package org.yzhang3.data.compressor;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.zip.ZipException;

import org.yzhang3.data.bean.HuffmanTree;
import org.yzhang3.data.common.CompressorAdapter;
import org.yzhang3.data.common.Constants;
import org.yzhang3.data.utils.BinaryUtils;
import org.yzhang3.data.utils.ByteUtils;
import org.yzhang3.data.utils.IntegerUtils;
import org.yzhang3.data.utils.StringUtils;

public class HuffmanCompressor extends CompressorAdapter {
	
	@Override
	public void compressFile(String sourcePath, String targetPath) throws ZipException {
		Map<Integer, Integer> counterMap = countByteFrequence(sourcePath);
		
		HuffmanTree huffmanTree = new HuffmanTree(counterMap);
		
		Map<Integer, String> alphabet = huffmanTree.alphabet();
		
		if (Constants.isPrintEnable) {
			printCompressAlphabet(alphabet);
		}
		
		InputStream is = null;
		OutputStream os = null;
		try {
			is = new FileInputStream(sourcePath);
			os = new FileOutputStream(targetPath);
			
			
			// 1. write alphabet(data - encodings)
			writeAlphabet(alphabet, os);
			
			// 2. write input stream's all bytes' encodings
			int pieceLength = 1024 * 8;// 1M
			byte[] piece = new byte[pieceLength];
			byte[] encodingDataBytes = null;
			
			int readed = 0;
			String dataEncoding = null;
			StringBuilder sb = new StringBuilder();
			while ((readed = is.read(piece, 0, pieceLength)) > 0) {
				
				for (int i=0; i<readed; i++) {
					dataEncoding = alphabet.get(ByteUtils.toUnsignedInt(piece[i]));
					sb.append(dataEncoding);
				}
				
				encodingDataBytes = BinaryUtils.parseBinaryChainToBytes(sb);
				os.write(encodingDataBytes);
			}
			
			// 3. write rest bytes
			writeRestBinary(sb, os);
			
			os.flush();
		} catch (FileNotFoundException e) {
			throw new ZipException("Compression: " + sourcePath + " do not found!" + e.getMessage());
		} catch (IOException e) {
			throw new ZipException("Compression Excepton: " + e.getMessage());
		} finally {
			try {
				if (null != is) { is.close(); }
			} catch (IOException e) {
				e.printStackTrace();
			}
			try {
				if (null != os) { os.close(); }
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

	private void writeRestBinary(StringBuilder sb, OutputStream os) throws IOException {
		if (sb.length() == 0) {
			os.write(0);
		} else {
			if (sb.length() < Constants.BITS_PRE_BYTE) {
				String resetBinary = StringUtils.format(sb.toString(), -Constants.BITS_PRE_BYTE);
				os.write(IntegerUtils.toInt(resetBinary));
				int restLength = Constants.BITS_PRE_BYTE - sb.length();
				os.write(restLength);
				
				if (Constants.isPrintEnable) {
					System.out.println("Additional reset bits is " + sb.toString() + ", restLength = " + restLength);
				}
				
				sb.delete(0, sb.length());
			} else {
				throw new ZipException("Error: remaining string's length error, and error length is " + sb.length() + ".");
			}
		}
	}

	private void writeAlphabet(Map<Integer, String> alphabet, OutputStream os) throws IOException {
		
		int alphabetSize = alphabet.size();
		
		List<Integer> sortedDatas = new ArrayList<Integer>(alphabet.keySet());
		Collections.sort(sortedDatas);
		
		List<String> sortedEncodings = new ArrayList<String>(alphabetSize);
		int[] encodingLengths = new int[alphabetSize];
		
		int j=0;
		for (Integer data : sortedDatas) {
			sortedEncodings.add(alphabet.get(data));
			encodingLengths[j++] = alphabet.get(data).length();
//			System.out.print("" + alphabet.get(data).length() + ", ");
		}
		
		if (Constants.isPrintEnable) {
			System.out.println("Alphabet Size = " + alphabetSize + ", encodingLengths = " + IntegerUtils.sum(encodingLengths));
		}
		
		StringBuilder sb = new StringBuilder();
		
		// 1. write alphabet size as one byte
		if (alphabetSize == 256) {// 
			os.write(1);
		} else {
			os.write(0);
		}
		os.write(alphabetSize);
		
		if (Constants.isPrintEnable) {
			System.out.println("Alphabet Size Bianry = " + ByteUtils.toBinary(IntegerUtils.toByte(alphabetSize)) + ", byte = " + IntegerUtils.toByte(alphabetSize));
		}
		
		// 2. write all encodings' length
		byte[] alphLenBytes = IntegerUtils.toByte(encodingLengths);
		os.write(alphLenBytes);
		
		// 3. write all encodings
		for (String encoding : sortedEncodings) {
			sb.append(encoding);
		}
		if (sb.length() % Constants.BITS_PRE_BYTE != 0) {
			int n = (sb.length() / Constants.BITS_PRE_BYTE + 1) * Constants.BITS_PRE_BYTE - sb.length();
			for (int i=0; i<n; i++) {
				sb.append(Constants.BINARY_ZERO);
			}
		}
		if (Constants.isPrintEnable) {
			System.out.println("Compress encoding: " + sb.toString());
		}
		
		byte[] alphEncodingBytes = BinaryUtils.parseBinaryChainToBytes(sb);
		os.write(alphEncodingBytes);
		
		// 3. write all encodings' datas
		byte[] dataBytes = new byte[alphabetSize];
		for (int i=0; i<alphabetSize; i++) {
			dataBytes[i] = IntegerUtils.toByte(sortedDatas.get(i).intValue());
		}
		os.write(dataBytes);
	}

	private Map<Integer, Integer> countByteFrequence(String sourcePath) throws ZipException {
		Map<Integer, Integer> counterMap = new HashMap<Integer, Integer>();
		
		InputStream is = null;
		int[] counter = new int[257];// no 128, because byte is in [0 - 256]
		Arrays.fill(counter, 0);
		
		try {
			is = new FileInputStream(sourcePath);
			int pieceLength = 1024 * 1024;// 1M
			byte[] piece = new byte[pieceLength];
			int[] pieceInts = new int[pieceLength];
			int readed = 0;
			int data = 0;
			while ((readed = is.read(piece, 0, pieceLength)) > 0) {
				pieceInts = ByteUtils.toUnsignedInt(piece);
				for (int i=0; i<readed; i++) {
					data = pieceInts[i];
					counter[data] = counter[data] + 1;
				}
			}
		} catch (FileNotFoundException e) {
			throw new ZipException("Compression: " + sourcePath + " do not found!" + e.getMessage());
		} catch (IOException e) {
			throw new ZipException("Compression Excepton: " + e.getMessage());
		} finally {
			try {
				if (null != is) {
					is.close();
				}
			} catch (IOException e) {
				throw new ZipException("Compression: colse Input Stream exception!");
			}
		}
		
		for (int i=0; i<counter.length; i++) {
			if (0 == counter[i]) {
				continue;
			}
			counterMap.put(Integer.valueOf(i), Integer.valueOf(counter[i]));
		}
		
		return counterMap;
	}

	public static void main(String[] args) throws IOException {
		HuffmanCompressor huffmanZip = new HuffmanCompressor();
		
		String fileName = "JWFDv0.96.doc";// google.pdf JWFDv0.96.doc temp.txt Huffman.java
		String zipFileName = fileName + ".zip";
		String unzipFleName = "unzip_" + fileName;
		
		String sourcePath = "C:/Users/dell/Desktop/"+fileName;
		String zipPath = "C:/Users/dell/Desktop/"+zipFileName;
		String unzipPath = "C:/Users/dell/Desktop/"+unzipFleName;
		
//		huffmanZip.compress(sourcePath, zipPath);
		huffmanZip.decompressFile(zipPath, unzipPath);
		
	}

	@Override
	public void decompressFile(String sourcePath, String targetPath) throws ZipException {
		InputStream is = null;
		OutputStream os = null;
		try {
			is = new FileInputStream(sourcePath);
			os = new FileOutputStream(targetPath);
			
			// 1. read out alphabet
			Map<String, Integer> alphabet = readAlphabet(is);
			
			if (Constants.isPrintEnable) {
				printDecompressAlphabet(alphabet);
			}
			
			int[] encodingLengths = new int[alphabet.size()];
			int t = 0, minEncodingLength = Integer.MAX_VALUE, maxEncodingLength = Integer.MIN_VALUE;
			for (String en : alphabet.keySet()) {
				encodingLengths[t++] = en.length();
				if (en.length() < minEncodingLength) {
					minEncodingLength = en.length();
				}
				if (en.length() > maxEncodingLength) {
					maxEncodingLength = en.length();
				}
			}
			
			// 2. read all content
			int pieceLength = 1024 * 8;// 1M
			byte[] piece = new byte[pieceLength];
			List<Integer> datas = null;
			byte[] dataBytes = null;
			int readed = 0;
			
			Integer foundData = null;
			boolean isLast = false;
			int restLength = 0;
			
			int baseLength = Constants.BITS_PRE_INT;
			
			StringBuilder sb = new StringBuilder();
			while ((readed = is.read(piece, 0, pieceLength)) > 0) {
				if (is.available() == 0) {
					restLength = piece[readed - 1];
					isLast = true;
					readed = readed - 1;
				} else if (is.available() == 1) {
					restLength = is.read();
					isLast = true;
				}
				
				for (int i=0; i<readed; i++) {
					sb.append(ByteUtils.toBinary(piece[i]));
				}
				
				if (isLast) {
					if (0 < restLength) {
						System.out.println("Rest Length is " + restLength + ".");
						sb.delete(sb.length() - restLength, sb.length());
						isLast = false;
						restLength = 0;
					}
				}
				datas = new ArrayList<Integer>();
				while (sb.length() > baseLength) {// 
					foundData = findData(alphabet, sb, encodingLengths);
					if (null != foundData) {
						datas.add(foundData);
					} else {
						throw new IOException("Error: can not find expected data in alphabet! and minEncodingLength = " + minEncodingLength);
					}
				}
				dataBytes = IntegerUtils.toByteArray(datas);
				os.write(dataBytes);
			}
			
			dataBytes = handleUndecompressedBinary(sb, minEncodingLength, alphabet, encodingLengths);
			
			os.write(dataBytes);
			
			os.flush();
		} catch (FileNotFoundException e) {
			throw new ZipException("Compression: " + sourcePath + " do not found!" + e.getMessage());
		} catch (IOException e) {
			throw new ZipException("Compression Excepton: " + e.getMessage());
		} finally {
			try {
				if (null != is) { is.close(); }
			} catch (IOException e) {
				e.printStackTrace();
			}
			try {
				if (null != os) { os.close(); }
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		
	}
	
	private Map<String, Integer> readAlphabet(InputStream is) throws IOException {
		
		// 1. read alphabet size
		String alphSizeBinary = IntegerUtils.to8Bits(is.read())+IntegerUtils.to8Bits(is.read());
		System.out.println("alphSizeBinary = " + alphSizeBinary);
		int alphabetSize = IntegerUtils.toInt(alphSizeBinary);
		
		Map<String, Integer> alphabet = new HashMap<String, Integer>(alphabetSize);
		
		// 2. read alphabet all encodings' length
		byte[] alphLengthBytes = new byte[alphabetSize];
		is.read(alphLengthBytes);
		int[] alphLengthInts = ByteUtils.toUnsignedInt(alphLengthBytes);
		int sumLength = IntegerUtils.sum(alphLengthInts);
		
		if (Constants.isPrintEnable) {
			System.out.println("Alphabet Size = " + alphabetSize + ", sumLength = " + sumLength);
		}
		
		int minEncodingLength = Integer.MAX_VALUE;
		for (int i=0; i<alphLengthInts.length; i++) {
			if (alphLengthInts[i] < minEncodingLength) {
				minEncodingLength = alphLengthInts[i];
			}
		}
		
		// 3. read alphabet all encodings
		StringBuilder sb = new StringBuilder();
		int alphEncodingByteNum = sumLength / Constants.BITS_PRE_BYTE;
		if (sumLength % Constants.BITS_PRE_BYTE != 0) {
			alphEncodingByteNum = alphEncodingByteNum + 1;
		}
		byte[] alphEncodingBytes = new byte[alphEncodingByteNum];
		is.read(alphEncodingBytes);
		for (int i=0; i<alphEncodingBytes.length; i++) {
			sb.append(ByteUtils.toBinary(alphEncodingBytes[i]));
		}
		
		if (Constants.isPrintEnable) {
			System.out.println("Dompress encoding: " + sb.toString());
		}
		
		String[] alphEncodings = new String[alphabetSize];
		for (int i=0; i<alphLengthInts.length; i++) {
			alphEncodings[i] = sb.substring(0, alphLengthInts[i]);
			sb.delete(0, alphLengthInts[i]);
		}
		if (Constants.isPrintEnable) {
			System.out.println("rest encoding string: " + sb.toString());
		}
		sb.delete(0, sb.length());// delete all
		
		// 4. read alphabet all data
		byte[] alphDataBytes = new byte[alphabetSize];
		is.read(alphDataBytes);
		int[] alphDataInts = ByteUtils.toUnsignedInt(alphDataBytes);
		
		for (int i=0; i<alphabetSize; i++) {
			alphabet.put(alphEncodings[i], Integer.valueOf(alphDataInts[i]));
		}
		
		return alphabet;
	}
	
	/**
	 * TODO: in some times, it will remains some rest binary in <code>sb</code>, but it do not have impact on file compression.<br>
	 * I do not know the reason. 
	 * @param sb
	 * @param minEncodingLength
	 * @param alphabet
	 * @param encodingLengths
	 * @return
	 */
	private byte[] handleUndecompressedBinary(StringBuilder sb, int minEncodingLength, Map<String, Integer> alphabet, int[] encodingLengths) {

		if (Constants.isPrintEnable) {
			System.out.println("Decompress rest sb = " + sb.toString());
		}
		
		int lastByteCount = sb.length()/minEncodingLength+1;
		List<Integer> datas = new ArrayList<Integer>();
		Integer foundData = null;
		for (int i=0; i<lastByteCount; i++) {
			if (sb.length() > 0) {
				foundData = findData(alphabet, sb, encodingLengths);
				if (null != foundData) {
					datas.add(foundData);
				} else {
					System.out.println("Error: can not find expected data in alphabet! and minEncodingLength = " + minEncodingLength);
				}
				
				System.out.println("And rest sb is " + sb.toString() + ".");
			} else {
				break;
			}
		}
		
		byte[] dataBytes = IntegerUtils.toByteArray(datas);
		
		if (Constants.isPrintEnable) {
			System.out.println("Decompress rest data is " + datas );
			System.out.println("And rest & last sb is " + sb.toString());
		}
		
		return dataBytes;
	}

	private Integer findData(Map<String, Integer> alphabet, StringBuilder sb, int[] alphLengthInts) {
		Integer foundData = null;
		String tryingEncoding = null;
		for (int i=0; i<alphLengthInts.length; i++) {
			if (sb.length() >= alphLengthInts[i]) {
				tryingEncoding = sb.substring(0, alphLengthInts[i]);
				if (alphabet.containsKey(tryingEncoding)) {
					foundData = alphabet.get(tryingEncoding);
					sb.delete(0, alphLengthInts[i]);
					break;
				}
			}
		}
		return foundData;
	}
	
	private void printDecompressAlphabet(Map<String, Integer> alphabet) {
		int maxEncodingLength = 0, minEncodingLength = Integer.MAX_VALUE;
		String maxEncoding = "", minEncoding = "";
		int j=1;
		
		List<Integer> sortedDataKeys = new ArrayList<Integer>(alphabet.values());
		Collections.sort(sortedDataKeys);
		

		Map<Integer, String> al = new HashMap<Integer, String>(alphabet.size());
		
		for (Entry<String, Integer> e : alphabet.entrySet()) {
			al.put(e.getValue(), e.getKey());
		}
		
		String encoding = null;
		for (Integer e : sortedDataKeys) {
			encoding = al.get(e);
			if (encoding.length() > maxEncodingLength) {
				maxEncodingLength = encoding.length();
				maxEncoding = encoding;
			}
			if (encoding.length() < minEncodingLength) {
				minEncodingLength = encoding.length();
				minEncoding = encoding;
			}
			System.out.print("{d: " + e + ", e: " + encoding + "}");
			if (j%3 == 0) {
				System.out.println("");
			} else {
				System.out.print("\t");
			}
			j++;
		}
		System.out.println();
		
		System.out.println("maxEncoding = " + maxEncoding + " and length is " + maxEncoding.length());
		System.out.println("minEncoding = " + minEncoding + " and length is " + minEncoding.length());
	}
	
	private void printCompressAlphabet(Map<Integer, String> alphabet) {
		int maxEncodingLength = 0, minEncodingLength = Integer.MAX_VALUE;
		String maxEncoding = "", minEncoding = "";
		int j=1;
		
		List<Integer> sortedKeys = new ArrayList<Integer>(alphabet.keySet());
		Collections.sort(sortedKeys);
		
		String encoding = null;
		for (Integer e : sortedKeys) {
			encoding = alphabet.get(e);
			if (encoding.length() > maxEncodingLength) {
				maxEncodingLength = encoding.length();
				maxEncoding = encoding;
			}
			if (encoding.length() < minEncodingLength) {
				minEncodingLength = encoding.length();
				minEncoding = encoding;
			}
			System.out.print("{d: " + e + ", e: " + encoding + "}");
			if (j%3 == 0) {
				System.out.println("");
			} else {
				System.out.print("\t");
			}
			j++;
		}
		System.out.println();
		
		System.out.println("maxEncoding = " + maxEncoding + " and length is " + maxEncoding.length());
		System.out.println("minEncoding = " + minEncoding + " and length is " + minEncoding.length());
	}

	@Override
	public String compressText(String originalText) throws ZipException {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public String decompressText(String compressedText) throws ZipException {
		// TODO Auto-generated method stub
		return null;
	}
	
	
	
}
